#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// 堆结构定义
typedef struct
{
    int *array;   // 存储堆元素的数组
    int capacity; // 堆的最大容量
    int size;     // 堆当前大小
} MaxHeap;

// 交换两个元素的值
void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 上浮操作，维护堆性质
void heapifyUp(MaxHeap *H, int index)
{
    while (index > 0)
    {
        int parent = (index - 1) / 2;
        if (H->array[parent] >= H->array[index])
        {
            break;
        }
        swap(&H->array[parent], &H->array[index]);
        index = parent;
    }
}

// 下沉操作，维护堆性质
void heapifyDown(MaxHeap *H, int index)
{
    while (2 * index + 1 < H->size)
    {
        int left = 2 * index + 1;
        int right = 2 * index + 2;
        int largest = index;

        if (left < H->size && H->array[left] > H->array[largest])
        {
            largest = left;
        }

        if (right < H->size && H->array[right] > H->array[largest])
        {
            largest = right;
        }

        if (largest == index)
        {
            break;
        }

        swap(&H->array[index], &H->array[largest]);
        index = largest;
    }
}

// 插入元素
void HeapInsert(MaxHeap *H, int value, int index)
{
    // 检查是否需要扩容
    if (H->size >= H->capacity)
    {
        H->capacity *= 2;
        H->array = (int *)realloc(H->array, H->capacity * sizeof(int));
        printf("Heap capacity expanded to %d\n", H->capacity);
    }

    // 插入新元素并上浮
    H->array[H->size] = value;
    heapifyUp(H, H->size);
    H->size++;
}

// 构建堆
void BuildHeap(MaxHeap *H, int arr[], int n)
{
    // 分配内存
    H->array = (int *)malloc(n * sizeof(int));
    H->capacity = n;
    H->size = 0;

    // 将元素插入堆中
    for (int i = 0; i < n; i++)
    {
        HeapInsert(H, arr[i], i);
    }
}

// 销毁堆
void DestroyHeap(MaxHeap *H)
{
    free(H->array);
    H->array = NULL;
    H->capacity = 0;
    H->size = 0;
}

// 删除堆顶元素
bool HeapExtractMax(MaxHeap *H, int *value)
{
    if (H->size == 0)
    {
        printf("Heap is empty, cannot extract max\n");
        return false;
    }

    *value = H->array[0];
    H->array[0] = H->array[H->size - 1];
    H->size--;
    heapifyDown(H, 0);

    return true;
}

// 获取堆顶元素
int HeapPeek(MaxHeap *H)
{
    if (H->size == 0)
    {
        printf("Heap is empty\n");
        return -1;
    }
    return H->array[0];
}

// 获取堆大小
int HeapSize(MaxHeap *H)
{
    return H->size;
}

// 打印堆内容
void PrintHeap(MaxHeap *H)
{
    printf("Heap content: ");
    for (int i = 0; i < H->size; i++)
    {
        printf("%d ", H->array[i]);
    }
    printf("\n");
}

int main()
{
    MaxHeap H;
    int arr[] = {3, 2, 1, 5, 6, 4};
    int n = sizeof(arr) / sizeof(arr[0]);

    // 构建堆
    printf("Building heap from array: ");
    for (int i = 0; i < n; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");

    BuildHeap(&H, arr, n);
    PrintHeap(&H);
    printf("Heap size: %d\n", HeapSize(&H));

    // 获取堆顶元素
    printf("Peek top element: %d\n", HeapPeek(&H));

    // 插入新元素
    printf("Inserting element 7\n");
    HeapInsert(&H, 7, H.size);
    PrintHeap(&H);
    printf("Heap size: %d\n", HeapSize(&H));

    // 提取最大值
    int max;
    if (HeapExtractMax(&H, &max))
    {
        printf("Extracted max element: %d\n", max);
    }
    PrintHeap(&H);
    printf("Heap size: %d\n", HeapSize(&H));

    // 再次提取最大值
    if (HeapExtractMax(&H, &max))
    {
        printf("Extracted max element: %d\n", max);
    }
    PrintHeap(&H);

    // 销毁堆
    DestroyHeap(&H);
    printf("Heap destroyed. Size: %d\n", HeapSize(&H));

    return 0;
}